#include<vector>

using std::vector;
struct ListNode
{
    int val;
    ListNode *next;
    ListNode() : val(0), next(nullptr) {}
    ListNode(int x) : val(x), next(nullptr) {}
    ListNode(int x, ListNode *next) : val(x), next(next) {}
};


class Solution {
public:
    bool isPalindrome(ListNode* head) {
        if (!head || !head->next) return head;
        // find median
        ListNode* slowptr = head;
        ListNode* fastptr = head;
        ListNode* med0, *med1;
        ListNode* extraPtr = nullptr;

        int N = 1;
        // 快慢指针找中间节点
        while (true) {
            for (int i = 0; i < 2 && fastptr->next; i++) {
                fastptr = fastptr->next;
                N++;
            }
            if (!fastptr->next && N % 2 == 0) {
                // 为偶数的情况
                med0 = slowptr;
                med1 = slowptr->next;
                break;
            }
            else if (!fastptr->next) {
                // 奇数情况，必须分开
                med0 = slowptr;
                med1 = slowptr->next->next;
                extraPtr = slowptr->next;
                break;
            }
            else slowptr = slowptr->next;
        }

        bool flag = false;
        med0->next = nullptr;
        // 反转链表
        med0 = reverse(head);
        flag = check(med0, med1);
        // recover
        head = reverse(med0);
        
        if (N%2 == 0) {    
            med0->next = med1;
        }
        else {
            med0->next = extraPtr;
        }
        return flag;
    }

    bool check(ListNode* a, ListNode* b) {
        while (true) {
            if ((a && !b) || (!a && b)) return false;
            if (!a && !b) return true;
            if (a->val == b->val) {
                a = a->next;
                b = b->next;
            }
            else return false;
        }
        return true;
        
    }

    ListNode* reverse(ListNode* head) {
        if (!head || !head->next) return head;
        ListNode* pre = nullptr;
        ListNode* cur = head;
        while (cur) {
            ListNode* tmp = cur->next;
            cur->next = pre;
            pre = cur;
            if (tmp) cur = tmp;
            else break;
        }
        return cur;

    }
};


int main() {
    
}